package first.codeTop.alibaba;

/**
 * @ClassName LC543
 * @description:
 * @author: 荣燊
 * @create: 2021-10-18 20:57
 **/
public class LC543 {
    // 二叉树直径，就是统计左子树的高度和右子树的高度,
    // 有一种情况就是不穿过根节点，那么就要维护一个最大的值记录
    static int max = 0;

    public static int diameterOfBinaryTree(TreeNode root) {
        max = 1;
        dfs(root);
        return max-1;
    }

    public static int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        max = Math.max(max, l+r+1);
        return Math.max(l, r) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(dfs(root.left));
    }
}
